package com.mgq.algorithm.dp;

/**
 * 最长有效括号 LeetCode 32题
 */
public class LongestValidParentheses {

    public static int longestValidParentheses(String str) {
        char[] chars = str.toCharArray();
        int[] dp = new int[chars.length];
        dp[0]=0;
        int max=0;
        for (int i = 1; i < chars.length; i++) {
            //左括号直接就是0;
            if (chars[i] == ')') {
                //右括号
                //先看i-1位置的值是多少
                int f=dp[i-1];
                int p = i - dp[i - 1]-1;
                if (p>=0&& chars[p] == '(') {
                    //说明是正确的.
                    //还需要把p-1位置的值接上
                    dp[i]=2+f;
                    if (p > 0) {
                        dp[i] += dp[p - 1];
                    }
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    public static void main(String[] args) {
        //System.out.println(longestValidParentheses("(())"));
       // System.out.println(longestValidParentheses("())"));
        System.out.println(longestValidParentheses(")()())()()("));
    }
}
